package leetcode._01_数组._02_romove_num;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/1/16 16:27
 * 给出了一个由小写字母组成的字符串 S。然后，我们可以进行任意次数的移动。
 * 在每次移动中，我们选择前 K 个字母中的一个（从左侧开始），将其从原位置移除，并放置在字符串的末尾。
 * 返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。

 * 示例 1：
 * 输入：S = "cba", K = 1
 * 输出："acb"
 * 解释：
 * 在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
 * 在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。
 *
 *
 * 示例 2：
 * 输入：S = "baaca", K = 3
 * 输出："aaabc"
 * 解释：
 * 在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
 * 在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

 */
public class _899_有序队列 {
    public static void main(String[] args){
        String[] s = {"benb","dbcea","cbca","acdb","cba","baaca","dabc"};
        int[] res = {2,2,3,4,1,3,1};
        String[] t = {"bben","abcde","abcc","abcd","acb","aaabc","abcd"};
        for (int i = 4; i < s.length; i++) {
            String s1 = orderlyQueue_3(s[i], res[i]);
            System.out.println(s1.equals(t[i]));
        }
    }

    /*认准思路--可以使用s1.compareTo(s2)来比较两个字符串*/
    public static String orderlyQueue_3(String s, int k) {
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        if(k > 1){
            return new String(ch);
        }
        String ans = s;
        for (int i = 1; i < ch.length; i++) {
            String temp = s.substring(i) + s.substring(0, i);
            if(temp.compareTo(ans) < 0){
                ans = temp;
            }
        }
        return ans;
    }

    /*思路错误*/
    public static String orderlyQueue_2(String s, int k) {
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        if( k == 1){
            int minIndex = -1;
            char curNext = 'z' + 1;
            for (int i = 0; i < ch.length; i++) {
                if(ch[0] == s.charAt(i)){
                   int nextIndex = (i+1)%s.length();

                    if(s.charAt(nextIndex) < curNext){
                       curNext = s.charAt(nextIndex);
                       minIndex = i;
                   }
                }
            }
            return s.substring(minIndex) + s.substring(0,minIndex);
        }
        StringBuilder sori = new StringBuilder(s);
        StringBuilder res = new StringBuilder(String.valueOf(ch[0]));
        sori.deleteCharAt(s.lastIndexOf(ch[0]));
        while (sori.length() > 0){
            char[] prech = sori.substring(0, Math.min(k,sori.length())).toCharArray();
            Arrays.sort(prech);
            res.append(prech[0]);
            sori.deleteCharAt(sori.indexOf(String.valueOf(prech[0])));
        }
        return String.valueOf(res);
    }
    public static String orderlyQueue(String s, int k) {
        char[] ch = s.toCharArray();
        Arrays.sort(ch);
        if( k >= s.length()){
            return new String(ch);
        }
        String minS = new String(ch).substring(0, k);

        if(s.substring(0,k).equals(minS)){
            return s;
        }
        char[] chpre = s.substring(0, k).toCharArray();
        Arrays.sort(chpre);
        String spre = new String(chpre, 0, k - 1);
        String nextS = spre + s.substring(k) + chpre[k-1];
        return orderlyQueue(nextS,k);
    }
}
